package offer;

public class _04_二维数组中的查找 {
    public static void main(String[] args) {
//        int[][] matrix = {{1, 4, 7, 11, 15},
//                {2, 5, 8, 12, 19},
//                {3, 6, 9, 16, 22},
//                {10, 13, 14, 17, 24},
//                {18, 21, 23, 26, 30}};
//        int target = 5;
        int[][] matrix = {{1, 2, 3, 4, 5},
                          {6, 7, 8, 9, 10},
                          {11, 12, 13, 14, 15},
                          {16, 17, 18, 19, 20},
                          {21, 22, 23, 24, 25}};
        int target = 19;
        Solution solution = new _04_二维数组中的查找().new Solution();
        System.out.println(solution.findNumberIn2DArray(matrix, target));
    }

    // Z字型查找
    class Solution {

        public boolean findNumberIn2DArray(int[][] matrix, int target) {
            if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return false;
            int i = 0;
            int j = matrix[0].length - 1;
            while (i < matrix.length && j >= 0) {
                if (matrix[i][j] == target) {
                    return true;
                } else if (matrix[i][j] < target) {
                    i++;
                } else if (matrix[i][j] > target) {
                    j--;
                }
            }
//            if (i == matrix.length || j == 1) {
//                return false;
//            }
            return false;
        }
    }

    // 逐行二分
    class Solution1 {

        public boolean findNumberIn2DArray(int[][] matrix, int target) {
            for (int[] nums : matrix) {
                if (binarySearch(nums, target)) {
                    return true;
                }
            }
            return false;
        }

        private boolean binarySearch(int[] matrix, int target) {
            int l = 0;
            int r = matrix.length - 1;
            while (l <= r) {
                int mid = l + (r - l) / 2;
                if (matrix[mid] == target) {
                    return true;
                } else if (matrix[mid] < target) {
                    l = mid + 1;
                } else {
                    r = mid - 1;
                }
            }
            return false;
        }
    }
}
